// https://www.lintcode.com/problem/interval-sum/description
// 206. 区间求和 I
// 给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end] 。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的总和，并返回在结果列表中。

// 样例
// 对于数组 [1,2,7,8,5]，查询[(1,2),(0,4),(2,4)], 返回 [9,23,20]

// 挑战
// O(logN) time for each query



/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class MyTreeNode {
    public:
        int start, end;
        long long sum;
        MyTreeNode *left, *right;
        MyTreeNode(int start, int end, long long sum) {
            this->start = start;
            this->end = end;
            this->sum = sum;
            this->left = this->right = NULL;
        }
};

class SegmentTree {
    public:
        static MyTreeNode* build(int start, int end, vector<int> A) 
        {
            if (start > end)
            {
                return NULL;
            }
            MyTreeNode* root = new MyTreeNode(start, end, A[start]);
            if (start != end)
            {
                int mid = (start + end) / 2;
                root->left = build(start, mid, A);
                root->right = build(mid + 1, end, A);
                root->sum = root->left->sum + root->right->sum;
            }
            return root;
        }
        
        static long long query(MyTreeNode* root, int start, int end)
        {
            if (start <= root->start && end >= root->end)
            {
                return root->sum;
            }
            else if (start > root->end || end < root->start)
            {
                return 0L;
            }
            else
            {
                return query(root->left, start, end) + query(root->right, start, end);
            }
        }
};

class Solution {
public:
    /**
     * @param A: An integer list
     * @param queries: An query list
     * @return: The result list
     */
    // vector<long long> intervalSum(vector<int> &A, vector<Interval> &queries) {
    //     // 法一：前缀和数组
    //     vector<long long> result;
    //     vector<long long> sum;
    //     sum.push_back(0);
    //     for (int i = 0; i < A.size(); i++)
    //     {
    //         sum.push_back(A[i] + sum.back());
    //     }
    //     for (Interval i: queries)
    //     {
    //         result.push_back(sum[i.end + 1] - sum[i.start]);
    //     }
    //     return result;
        
    // }
    
    
    // 法二：线段树
    // Time Limit Exceeded 90% 数据通过测试

    
    
    vector<long long> intervalSum(vector<int> &A, vector<Interval> &queries) {
        vector<long long> result;
        MyTreeNode* root = SegmentTree::build(0, A.size() - 1, A); 
        for (int i = 0; i < queries.size(); ++i)
        {
            result.push_back(SegmentTree::query(root, queries[i].start, queries[i].end));
        }
        return result;
    }
};